#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
    int minimizeMax(std::vector<int>& nums, int p) {
        std::sort(nums.begin(), nums.end());
        struct Check {
            const std::vector<int>& nums;
            int p;
            Check(const std::vector<int>& nums, int p) : nums(nums), p(p) {}
            bool operator()(int mx) const {
                int cnt = 0;
                for (int i = 0; i < static_cast<int>(nums.size()) - 1; i++) {
                    if (nums[i + 1] - nums[i] <= mx) {
                        cnt++;
                        i++;
                    }
                }
                return cnt >= p;
            }
        };
        Check check(nums, p);
        int left = 0, right = nums.back() - nums[0];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
int main() {
    Solution sol;
    std::vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(3); 
    nums.push_back(4);
    int p = 2;
    int result = sol.minimizeMax(nums, p);
    std::cout << "The minimized maximum difference is: " << result << std::endl;
    return 0;
}
